home *** CD-ROM | disk | FTP | other *** search
/ Mac-Source 1994 July / Mac-Source_July_1994.iso / C and C++ / Libraries / objects in c ƒ / Name Sources / HashTable.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-03-06  |  4.1 KB  |  196 lines  |  [TEXT/KAHL]
  1. /*    
  2.  *        HashTable abstract class
  3.  *
  4.  *        Hash-based object association structure.  
  5.  *
  6.  *            Copyright © John Wainwright 1988
  7.  *
  8.  *    SuperClasses :
  9.  *
  10.  *  Instance Vars :
  11.  *                    table
  12.  *                    size
  13.  *                    hashType
  14.  *    Class Vars :
  15.  *    
  16.  *    Methods :
  17.  *                    new s t            - creates a hashtable of size & type
  18.  *                    get k            - gets the keyed value
  19.  *                    bind k v        - create a binding
  20.  *                    softBind k v     - create a binding only if not there
  21.  *                    push k v        - push v onto the keyed list
  22.  *                    getBinding k     - return the binding keyed by k
  23.  *                    sequence        - setup sequence
  24.  *                    next            - next key in sequence
  25.  *                    nextBinding        - next binding in sequence
  26.  *                    dispose            
  27.  *    Class Methods :
  28.  *
  29.  */
  30.  
  31. #include "oic.h"
  32. #include "generics.h"
  33. #include "names.h"
  34.  
  35. class     HashTable;                    /* the HashTable class                 */
  36.  
  37. #define TABLE_SIZE    255
  38.  
  39. struct HashTable_i                    /* HashTable instance structure        */
  40. {
  41.     object    *table;                    /* array of bindings                */
  42.     int        size;                    /* table size                        */
  43.     int        hashType;                /* hashing technique                */
  44.     int        seqCursor;                /* cursor used for sequencing        */
  45. };
  46. typedef struct HashTable_i HashTable_i;
  47.  
  48. /* -------------------- HashTable Instance methods ------------------- */
  49.  
  50. method object
  51. _new(self, h, ha)
  52.     object                    self;
  53.     register HashTable_i    *h;
  54.     register struct { int size, type; } *ha;
  55. {
  56.     /* the following should be fixed to make it the next largest prime */
  57.     h->size = ((ha->size + TABLE_SIZE - 1) / TABLE_SIZE) * TABLE_SIZE;
  58.     
  59.     h->table = (object *)scalloc(h->size * sizeof(object *));
  60.     h->hashType = ha->type;
  61.     
  62.     return self;
  63. }
  64.  
  65. method object
  66. _get(self, h, key)
  67.     object                    self;
  68.     register HashTable_i    *h;
  69.     register object         *key;
  70. {
  71.     register object *b;
  72.     
  73.     b = h->table + (int)hashOf(*key) % h->size;
  74.     for (; *b != NULL && !isKey(*b, *key); b++)
  75.         if (b >= h->table + h->size)
  76.             b = h->table;
  77.     return (*b == NULL) ? NULL : valueOf(*b);
  78. }
  79.  
  80. method object
  81. _getBinding(self, h, key)
  82.     object                    self;
  83.     register HashTable_i    *h;
  84.     register object         *key;
  85. {
  86.     register object *b;
  87.     
  88.     b = h->table + (int)hashOf(*key) % h->size;
  89.     for (; *b != NULL && !isKey(*b, *key); b++)
  90.         if (b >= h->table + h->size)
  91.             b = h->table;
  92.     return *b;
  93. }
  94.  
  95. method object
  96. _bind(self, h, ha)
  97.     object                    self;
  98.     register HashTable_i    *h;
  99.     register struct { object key, value; } *ha;
  100. {
  101.     register object *b;
  102.     register int     i;
  103.     
  104.     b = h->table + (int)hashOf(ha->key) % h->size;
  105.     for (i = 0; *b != NULL && !isKey(*b, ha->key) && i < h->size; b++, i++)
  106.         if (b >= h->table + h->size)
  107.             b = h->table;
  108.     
  109.     if (i == h->size)
  110.         return bind(enlarge(self), ha->key, ha->value);
  111.     else
  112.     {        
  113.         if (*b == NULL)
  114.             *b = New(Binding, ha->key, ha->value);
  115.         else
  116.             set(*b, ha->value);
  117.         return *b;
  118.     }
  119. }
  120.  
  121. method object
  122. _softBind(self, h, ha)
  123.     object                    self;
  124.     register HashTable_i    *h;
  125.     register struct { object key, value; } *ha;
  126. {
  127.     register object *b;
  128.     register int     i;
  129.     
  130.     b = h->table + (int)hashOf(ha->key) % h->size;
  131.     for (i = 0; *b != NULL && !isKey(*b, ha->key) && i < h->size; b++, i++)
  132.         if (b >= h->table + h->size)
  133.             b = h->table;
  134.     
  135.     if (i == h->size)
  136.         return softBind(enlarge(self), ha->key, ha->value);
  137.     else
  138.     {        
  139.         if (*b == NULL)
  140.             *b = New(Binding, ha->key, ha->value);
  141.         return *b;
  142.     }
  143. }
  144.  
  145. method object
  146. _sequence(self, h)                    /* reset sequence start                            */
  147.     object                    self;
  148.     register HashTable_i    *h;
  149. {
  150.     h->seqCursor = 0;
  151.     
  152.     return self;
  153. }
  154.  
  155. method object
  156. _next(self, h)                        /* next key from sequence                        */
  157.     object                    self;
  158.     register HashTable_i    *h;
  159. {
  160.     register object binding;
  161.     
  162.     while (h->seqCursor < h->size && (binding = h->table[h->seqCursor]) == NULL)
  163.         h->seqCursor++;
  164.     if (h->seqCursor++ < h->size)
  165.         return keyOf(binding);
  166.     else
  167.         return NULL;
  168. }
  169.  
  170. method object
  171. _dispose(self, h)
  172.     object                    self;
  173.     register HashTable_i    *h;
  174. {
  175.     free(h->table);
  176.     Super(self);
  177. }
  178.  
  179. /* ------------------- Init the HashTable class ---------------------- */
  180.  
  181. InitHashTableClass()
  182. {
  183.     HashTable = NewClass(sizeof(HashTable_i), 0, "HashTable", END);
  184.     AddMethods(HashTable,
  185.         newGeneric,         _new,
  186.         getGeneric,         _get,
  187.         bindGeneric,         _bind,
  188.         softBindGeneric,     _softBind,
  189.         getBindingGeneric,     _getBinding,
  190.         nextGeneric,         _next,
  191.         sequenceGeneric,     _sequence,
  192.         disposeGeneric,     _dispose,
  193.         END);
  194. }
  195.  
  196.